package java;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Question30 {
    public static void main(String[] args) {
        String s = "barfoothefoobarman";
        String[] strs = {"foo","bar"};
        List<Integer> list = findSubstring(s,strs);
        List<Integer> list1 = findSubstring1(s,strs);
        List<Integer> list2 = myFindSubstring1(s,strs);
        for (Integer item :
                list2) {
            System.out.println(item);
        }

    }

    private static List<Integer> myFindSubstring1(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (s == null || s.length() < 1){
            return res;
        }
        if (words == null || words.length < 1){
            return res;
        }

        int wordsNum = words.length;
        int wordLength = words[0].length();
        int subStrLength = wordsNum * wordLength;
        if (s.length() < subStrLength){
            return res;
        }

        Map<String,Integer> map = new HashMap<>();
        for (int i = 0 ; i < wordsNum ; i++){
            if (map.containsKey(words[i])){
                map.put(words[i],map.get(words[i]) + 1);
            }else {
                map.put(words[i],1);
            }
        }

        for (int i = 0; i < s.length() - subStrLength + 1 ; i ++){
            if (isMatchStr(s.substring(i,i + subStrLength),map,wordLength)){
                res.add(i);
            }
        }
        return res;
    }

    private static boolean isMatchStr(String subString, Map<String, Integer> map, int wordLength) {
        Map<String, Integer> mapTemp = new HashMap<>(map);
        for (int i = 0;i < subString.length() ; i ++){
            String key = subString.substring(i,i + wordLength);
            if (mapTemp.containsKey(key)){
                if (mapTemp.get(key) >= 1){
                    mapTemp.put(key,mapTemp.get(key) - 1);
                }else {
                    return false;
                }
            }else {
                return false;
            }
            i = i + wordLength - 1;
        }
        return true;
    }

    private static List<Integer> findSubstring1(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        int wordNum = words.length;
        if (wordNum == 0) {
            return res;
        }
        int wordLen = words[0].length();
        //HashMap1 存所有单词
        HashMap<String, Integer> allWords = new HashMap<String, Integer>();
        for (String w : words) {
            int value = allWords.getOrDefault(w, 0);
            allWords.put(w, value + 1);
        }
        //遍历所有子串
        for (int i = 0; i < s.length() - wordNum * wordLen + 1; i++) {
            //HashMap2 存当前扫描的字符串含有的单词
            HashMap<String, Integer> hasWords = new HashMap<String, Integer>();
            int num = 0;
            //判断该子串是否符合
            while (num < wordNum) {
                String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);
                //判断该单词在 HashMap1 中
                if (allWords.containsKey(word)) {
                    int value = hasWords.getOrDefault(word, 0);
                    hasWords.put(word, value + 1);
                    //判断当前单词的 value 和 HashMap1 中该单词的 value
                    if (hasWords.get(word) > allWords.get(word)) {
                        break;
                    }
                } else {
                    break;
                }
                num++;
            }
            //判断是不是所有的单词都符合条件
            if (num == wordNum) {
                res.add(i);
            }
        }
        return res;
    }



    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (s == null || s.length() < 1){
            return res;
        }
        if (words == null || words.length < 1){
            return res;
        }
        int wordsNum = words.length;
        String[] oneRes = new String[wordsNum];
        List<Integer> useIndex = new ArrayList<>();
        getIndex(res,oneRes,s,words,wordsNum,useIndex);
        return res;
    }

    private static void getIndex(List<Integer> res, String[] oneRes, String s, String[] words, int wordsNum, List<Integer> useIndex) {
        if (wordsNum < 1){
            StringBuilder oneResStr = new StringBuilder();
            for (int i = 0; i < oneRes.length; i++){
                oneResStr.append(oneRes[i]);
            }
            List<Integer> index = strStr(s,oneResStr.toString());
            if (index.size() != 0 ){
                for (Integer item :
                        index) {
                    if (!res.contains(item))
                    res.add(item);
                }
            }
            return;
        }

        for (int i = 0;i < words.length;i ++){
            if (!useIndex.contains(i)){
                oneRes[wordsNum - 1] = words[i];
                useIndex.add(i);
                getIndex(res,oneRes,s,words,wordsNum - 1,useIndex);
                useIndex.remove(useIndex.size() - 1);
            }
        }

    }
    public static List<Integer> strStr(String haystack, String needle) {
        List<Integer> res = new ArrayList<>();
        if (needle == null || needle.length() < 1) {
            return res;
        }
        if (haystack == null || haystack.length() < 1) {
            return res;
        }
        int needleLength = needle.length();
        for (int i = 0; i < haystack.length() - needleLength + 1; i ++){
            if (haystack.charAt(i) == needle.charAt(0) && isMatch(i,haystack,needle)){
                res.add(i);
            }
        }
        return res;
    }

    private static boolean isMatch(int i, String haystack, String needle) {
        for (int j = 0; j < needle.length() ; j ++){
            if (haystack.charAt(i + j) != needle.charAt(j)){
                return false;
            }
        }
        return true;
    }
}
